COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00004 ENDMK
C⊗;
\input macro[1,mps]
\input macrwf[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A92.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, September 22, 1989}
\leftline{\sevenrm Unpublished draft}
\bigskip
\noindent{\bf Obvious statement}

$a!$ is divisible by every number from 2 to $a$.

{\bf Theorem:}  The set of strings of composite length is not a CFL.

{\bf Proof:}  Suppose the set of strings of composite length is a CFL.  Then, 
texhout loss of generality, $L = \{ 1↑k \mid k$ is composite$\}\,$ is a CFL
with pumping constant $n-1>1$ (so that $n! > (n-1)!)$.

If $2 \leq d\leq n!$, $d$ divides $n!!$, and also divides $n!! + d$, so every
number from $n!! + 2$ to $n!! + n!$ is composite.  Let $p$ be the next prime
above $n!! + n!$; $p \geq n!! + n! + 1$; $p - (n-1)! \geq p - n! + 1 \geq n!!
+ 2$ is composite, $1↑{p-(n-1)!} \in L$, and can be pumped up to $1↑p \notin
L$, absurd.
\bye